Corelab Seminar
2015-2016
Dimitris Achlioptas
New Uses of Error-Correcting Codes
Abstract.
We consider the task of summing (integrating) an arbitrary
non-negative function over a discrete domain. This is a ubiquitous
task, known as partition function estimation in the context of graphical models. It is known that in a probabilistic approximate sense, summation can be reduced to maximization over random subsets of the domain defined by systems of linear equations modulo 2 (parity constraints).
Unfortunately, random parity constraints with many variables are
computationally intractable, while random parity constraints with few
variables have poor statistical performance.
We introduce two ideas to address these problems, both motivated by the
theory of error-correcting codes. The first idea exploits linearity to
exponentially reduce the size of the domain. The second idea, closer in
spirit to the original approach, is to use systems of linear equations
defining Low Density Parity Check (LDPC) codes. Even though the
equations in such systems only contain few variables each, their sets
of solutions (codewords) have excellent statistical properties. By
combining these ideas we achieve dramatic speedup over the original
approach and levels of accuracy that were completely unattainable
previously.
Based on joint work with Pei Jiang.